Feature #11: Generate Movie Viewing Orders
Implementing the "Generate Movie Viewing Orders" feature for our "Netflix" project.
We'll cover the following
Description#
We want to offer marathons for our viewers. Each marathon will have a fixed set of movies catering to a specific taste. For a given marathon, different viewing orders of the movies will yield different user satisfaction results. We want to experiment (A/B testing) with different viewing orders of the same marathon.
Your task is to generate all the possible permutations of movies in a given marathon.
Let’s look at an example to better understand this:
Solution#
To solve this problem, we will use the backtracking approach.
We will assume a Backtrack function that takes the index of the first movie to consider as an argument Backtrack(first).
-
If the first movie to consider has index
n, then that means that the current permutation is done. -
We will iterate over the marathon from index
Firstto indexn - 1. -
We will place the
ith movie first in the permutation, that is,Movies[First], Movies[i] = Movies[i], Movies[First]. -
We will proceed to create all the permutations that start from the
ith movie:Backtrack(First + 1). -
Now we will backtrack, that is,
Movies[First], Movies[i] = Movies[i], Movies[First]back.
Let’s look at some illustrations to better understand this:
Note: We are using numbers to represent movies in the following illustration.
1 of 14
2 of 14
3 of 14
4 of 14
5 of 14
6 of 14
7 of 14
8 of 14
9 of 14
10 of 14
11 of 14
12 of 14
13 of 14
14 of 14
Let’s look at the code for this solution:
Complexity measures#
| Time complexity | Space complexity |
|---|---|
Time complexity#
The algorithm takes time complexity, wherein is the Movies size and
Space complexity#
The algorithm will take space complexity because the maximum stack depth is , the height of any branch from the root to any leaf.